<!DOCTYPE html>
<html>
<head>
    <style>
        .graph-container {
            width: 600px;
            height: 400px;
            background: #f0f0f0;
            position: relative;
            border-radius: 8px;
        }
        .node {
            width: 40px;
            height: 40px;
            border-radius: 50%;
            background: #90CAF9;
            position: absolute;
            display: flex;
            align-items: center;
            justify-content: center;
            font-size: 16px;
            color: #333;
            transition: all 0.3s;
            cursor: pointer;
            border: 2px solid #1976D2;
        }
        .edge {
            position: absolute;
            height: 2px;
            background: #1976D2;
            transform-origin: left center;
            transition: all 0.3s;
        }
        .weight {
            position: absolute;
            background: white;
            padding: 2px 6px;
            border-radius: 10px;
            font-size: 12px;
            color: #333;
            box-shadow: 0 2px 4px rgba(0,0,0,0.1);
        }
        .distance-matrix {
            position: absolute;
            top: 10px;
            right: 10px;
            background: white;
            padding: 10px;
            border-radius: 8px;
            font-family: monospace;
            font-size: 12px;
            box-shadow: 0 2px 4px rgba(0,0,0,0.1);
        }
    </style>
</head>
<body style="margin: 0; display: flex; justify-content: center; align-items: center; height: 100vh; background: #f0f0f0;">
    <div class="graph-container" id="graph">
        <div class="distance-matrix" id="matrix"></div>
    </div>
    
    <script>
        // 图的节点数据
        const nodes = [
            { id: 0, x: 300, y: 50, label: 'A' },
            { id: 1, x: 150, y: 150, label: 'B' },
            { id: 2, x: 450, y: 150, label: 'C' },
            { id: 3, x: 100, y: 250, label: 'D' },
            { id: 4, x: 200, y: 250, label: 'E' },
            { id: 5, x: 400, y: 250, label: 'F' },
            { id: 6, x: 500, y: 250, label: 'G' },
            { id: 7, x: 300, y: 350, label: 'H' }
        ];

        // 图的边数据 [from, to, weight]
        const edges = [
            [0, 1, 4], [0, 2, 3],
            [1, 3, 6], [1, 4, 2], [1, 2, 5],
            [2, 5, 3], [2, 6, 7],
            [4, 7, 5], [5, 7, 4],
            [3, 4, 3], [5, 6, 2]
        ];

        // 创建图的可视化
        function createGraph() {
            const container = document.getElementById('graph');
            
            // 创建边和权重标签
            edges.forEach(([from, to, weight]) => {
                const edge = document.createElement('div');
                edge.className = 'edge';
                const fromNode = nodes[from];
                const toNode = nodes[to];
                
                const length = Math.sqrt(
                    Math.pow(toNode.x - fromNode.x, 2) + 
                    Math.pow(toNode.y - fromNode.y, 2)
                );
                const angle = Math.atan2(
                    toNode.y - fromNode.y,
                    toNode.x - fromNode.x
                );
                
                edge.style.width = `${length}px`;
                edge.style.left = `${fromNode.x + 20}px`;
                edge.style.top = `${fromNode.y + 20}px`;
                edge.style.transform = `rotate(${angle}rad)`;
                
                // 添加权重标签
                const weightLabel = document.createElement('div');
                weightLabel.className = 'weight';
                weightLabel.textContent = weight;
                weightLabel.style.left = `${fromNode.x + length/2}px`;
                weightLabel.style.top = `${fromNode.y + (toNode.y - fromNode.y)/2}px`;
                
                container.appendChild(edge);
                container.appendChild(weightLabel);
            });
            
            // 创建节点
            nodes.forEach(node => {
                const div = document.createElement('div');
                div.className = 'node';
                div.textContent = node.label;
                div.style.left = `${node.x}px`;
                div.style.top = `${node.y}px`;
                container.appendChild(div);
            });
        }

        // 更新距离矩阵显示
        function updateMatrix(dist, k = -1) {
            const matrix = document.getElementById('matrix');
            let html = '<table style="border-collapse: collapse;">';
            
            // 添加表头
            html += '<tr><td></td>';
            for (let i = 0; i < nodes.length; i++) {
                html += `<td style="padding: 4px; text-align: center;">${nodes[i].label}</td>`;
            }
            html += '</tr>';
            
            // 添加矩阵内容
            for (let i = 0; i < nodes.length; i++) {
                html += `<tr><td style="padding: 4px;">${nodes[i].label}</td>`;
                for (let j = 0; j < nodes.length; j++) {
                    const value = dist[i][j] === Infinity ? '∞' : dist[i][j];
                    const isHighlighted = k >= 0 && (i === k || j === k);
                    const style = isHighlighted ? 
                        'background: #FF4081; color: white;' : 
                        'background: white;';
                    html += `<td style="padding: 4px; text-align: center; ${style}">${value}</td>`;
                }
                html += '</tr>';
            }
            
            html += '</table>';
            matrix.innerHTML = html;
        }

        // Floyd-Warshall算法动画
        async function floydWarshall() {
            const nodeElements = document.querySelectorAll('.node');
            const edgeElements = document.querySelectorAll('.edge');
            
            // 初始化距离矩阵
            const dist = Array(nodes.length).fill().map(() => 
                Array(nodes.length).fill(Infinity)
            );
            
            // 设置直接连接的边的权重
            edges.forEach(([from, to, weight]) => {
                dist[from][to] = weight;
                dist[to][from] = weight;
            });
            
            // 设置自身到自身的距离为0
            for (let i = 0; i < nodes.length; i++) {
                dist[i][i] = 0;
            }
            
            // 显示初始矩阵
            updateMatrix(dist);
            await new Promise(resolve => setTimeout(resolve, 1000));
            
            // Floyd-Warshall算法主循环
            for (let k = 0; k < nodes.length; k++) {
                // 高亮中间节点
                nodeElements[k].style.backgroundColor = '#FF4081';
                
                for (let i = 0; i < nodes.length; i++) {
                    for (let j = 0; j < nodes.length; j++) {
                        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
                            const newDist = dist[i][k] + dist[k][j];
                            if (newDist < dist[i][j]) {
                                dist[i][j] = newDist;
                                
                                // 高亮更新的路径
                                if (i !== j) {
                                    nodeElements[i].style.backgroundColor = '#4CAF50';
                                    nodeElements[j].style.backgroundColor = '#4CAF50';
                                }
                            }
                        }
                    }
                }
                
                // 更新矩阵显示
                updateMatrix(dist, k);
                await new Promise(resolve => setTimeout(resolve, 1000));
                
                // 恢复节点颜色
                nodeElements[k].style.backgroundColor = '#90CAF9';
                for (let i = 0; i < nodes.length; i++) {
                    if (i !== k) {
                        nodeElements[i].style.backgroundColor = '#90CAF9';
                    }
                }
            }
        }

        // 初始化图并开始动画
        createGraph();
        setTimeout(floydWarshall, 1000);
        
        // 每15秒重置并重新开始
        setInterval(() => {
            const nodes = document.querySelectorAll('.node');
            const edges = document.querySelectorAll('.edge');
            
            nodes.forEach(node => {
                node.style.backgroundColor = '#90CAF9';
            });
            
            edges.forEach(edge => {
                edge.style.backgroundColor = '#1976D2';
            });
            
            setTimeout(floydWarshall, 1000);
        }, 15000);
    </script>
</body>
</html> 